package lib

import (
	"algorithms/ds"
	"strconv"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         257,
		Discription: "二叉树从根节点到叶子节点的所有路径",
		Level:       1,
		Labels: map[string]int{
			"二叉树": 1,
			"递归":  1,
		},
	})
}

func BinaryTreePaths(root *ds.TreeNode) []string {
	res := make([]string, 0)
	if root == nil {
		return res
	}

	var dfs func(*ds.TreeNode, string)
	dfs = func(node *ds.TreeNode, str string) {
		str += strconv.Itoa(node.Val) + "->"
		//注意只有两个孩子都未空才是叶子节点
		if node.Left == nil && node.Right == nil {
			res = append(res, str[:len(str)-2])
			return
		}

		if node.Left == nil {
			dfs(node.Right, str)
			return
		}

		if node.Right == nil {
			dfs(node.Left, str)
			return
		}

		dfs(node.Left, str)
		dfs(node.Right, str)
	}

	dfs(root, "")
	return res
}
